
// 673.最长递增子序列的个数
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        // 使用动态规划进行解决

        int n = nums.size();
        vector<int> len(n,1) , count(n,1) ;  
        int len_max = 1, count_max = 1;
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = 0 ; j < i ;j++)
            {
                if(nums[j] < nums[i])
                {
                    if(len[j] + 1 > len[i])
                        len[i] = len[j] + 1 , count[i] = count[j];
                    else if(len[j] + 1 == len[i]) count[i] += count[j];
                }
            }
            if(len[i] > len_max) 
                count_max = count[i] , len_max = len[i];
            else if(len_max == len[i]) count_max += count[i];
        }
        return count_max;
    }
};